

class Solution:
    """
    斐波那契数
    使用的记录前一步结果的解法，相对于数据记录结果和hash记录，提高了空间复杂度为O(1)
    """
    def fib(self, n: int) -> int:
        if n == 0 or n == 1:
            return n
        dp1 = 0; dp2 = 1
        for i in range(2, n + 1):
            dpi = dp2 + dp1
            dp1 = dp2
            dp2 = dpi
        return dp2


if __name__ == '__main__':
    s = Solution()
    print(s.fib(n=4))

